In the
computer science class, Yuri became very sad, so he came up with a game for
himself.
At the
beginning, he has an empty set. In each subsequent step, he thinks of a number
and checks whether it belongs to the set. If the number belongs to the set,
Yuri shouts “Yes”. If not, he shouts “No” and adds
it to the set. Before thinking of a new number, Yuri shouts the number of
elements in the set.
The
teacher got tired of Yuri's shouts, so he made him write a program that would
shout instead of him. But Yuri doesn’t know how
to program, so he asked you for help.
Input. The first
line contains one positive integer n
(1 ≤ n ≤ 105).
Each of the following n lines contains an integer that Yuri has thought
of. Yuri can only think of numbers in the range from -109 to 109.
Output. On a
separate line, print what Yuri would shout for each query.
|
Sample input 1 |
Sample output 1 |
|
5 1 2 3 4 1 |
No 1 No 2 No 3 No 4 Yes 4 |
|
|
|
|
Sample input 2 |
Sample output 2 |
|
3 1 1 1 |
No 1 Yes 1 Yes 1 |
set
data structure
In this
task, you must simulate the operations with the set. Let x
be the number thought of by Yuri. If x is already present in the set, print “Yes” and the size of the
set. Otherwise, add x to the set, print “No”, and the size of the set.
Algorithm
realization
Declare a set s.
set<int> s;
Read the number of queries n.
scanf("%d",&n);
Process the n queries sequentially.
for(i = 1; i <= n; i++)
{
Read the
number x that Yuri has thought of.
scanf("%d",&x);
If the number x
is not in the set s, add it to the set, print “No”, and the size of the set.
if(s.find(x)
== s.end())
{
s.insert(x);
printf("No %d\n",s.size());
}
else
If the number x
is present in the set s, print “Yes”
and the size of the set.
printf("Yes %d\n",s.size());
}
Java realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
TreeSet<Integer> s = new TreeSet<Integer>();
int n = con.nextInt();
for(int i = 0; i < n; i++)
{
int x = con.nextInt();
if (s.contains(x))
System.out.println("Yes " + s.size());
else
{
s.add(x);
System.out.println("No " + s.size());
}
}
con.close();
}
}
Python realization
Read the number of queries n.
n = int(input())
Declare a set s.
s = set({})
Process the n queries sequentially.
for _ in range(n):
Read the
number x that Yuri has thought of.
x
= int(input())
If the number x
is present in the set s, print “Yes”
and the size of the set.
if x in s:
print("Yes", end = ' ')
else:
If the number x
is not in the set s, add it to the set, print “No”, and the size of the set.
s.add(x)
print("No", end = ' ')
After the message “Yes” or “No”, print the size of the
set.
print(len(s))